1. Technical Field
The present invention relates to an uncoded bit decoding circuit and a branch metric processing circuit in a trellis decoding circuit which decodes trellis-coded modulated information symbols.
2. Background Art
A coded modulation technique is to improve transmission characteristics by optimally signal-arranging coded bit(s) and uncoded bit(s).
In the coded bits, the inter-signal distance can be easily provided by error correcting coding such as a block coding and convolutional coding. Therefore, among symbols which are located comparatively in close distance on constellation, the coded bits therefor may differ from other. On the other hand, as for the uncoded bits, they do not contain any effect intrinsic to the coding, so that the distance therebetween is determined on the constellation alone.
A basic function of signal arrangement in the coded modulation scheme is to maximize the distance for symbols (subset symbols) whose coding bit are the same. In other words, by maximizing the distance, the distance between the codes can also be expanded in an equivalent manner, so that a transmission mode whose transmission characteristic is preferable can be realized.
In the above-described coded modulation mode, presupposed is a multiple-valuedness of the modulation. On the other hand, in order to prevent a transmission band from expanding due to the coding operation, a modulation level need be increased, so that the transmission characteristic for the uncoded may be deteriorated. However, the improvement degree achieved by the above-described coding offsets and outweighs the deterioration of the transmission characteristic, thus generating a coding gain. Therefore, in the coded modulation mode, the coding gain can be comparatively easily obtained under band-limited channels, even in a case of utilizing the multiple-value modulation.
When a convolutional coding is used for the coding, it is generally called a trellis-coded modulation or TCM.
FIG. 21 shows a general construction for a trellis encoder. Referring to FIG. 21, information symbols (k+m) is divided to uncoded bits (k bits) and m bits which are fed to a convolutional coding unit 101, and the thus fed m bits are expanded to coded bits n, so that modulation symbols (k+n) are modulated and output therefrom.
The feature of trellis coded modulation proposed by G. Ungerboeck lies in that, referring to FIG. 1, how effectively the coded and uncoded bits are allocated to modulation symbols. The publication concerning G. Ungerboeck is, for example, available as "Channel coding with Multilevel/Phase Signals", IEEE Trans. Inform. Theory. Vol. IT-28, pp. 55-67, January 1982. The allocation originates in a "set-partitioning" technique. For example, the convolutional coding is utilized as a coding scheme in TCM, and configuration is determined such that the distance between the codes including the above-mentioned allocation, that is an Euclidean distance, is maximum. This is also known as "Ungerboeck code".
In "A pragmatic Approach to Trellis-Coded Modulation" (written by A. J. Viterbi, J. K. Wolf, E. Zehavi and R. Padovani, IEEE Communications Magazine, Vol. 27, pp. 11-19, July 1989), a coding scheme is designed so that, utilizing binary codes, an inter-code distance (Hamming distance) is maximum, and the convolutional codes are utilized for these TCM codes. This scheme is called "Pragmatic Code" because of its nature being practical.
FIG. 1 shows a general configuration of coding of TCM.
Referring to FIG. 1, input information symbol m.sub.0 bits all expanded to coded symbol n.sub.0 bits so as to be allocated to the modulation symbol. Then, coding rate R as a whole is such that R=m.sub.0 /n.sub.0. Moreover, as for code expansion, there is utilized the convolutional coding with coding rate r=m/n, where coding rate of the convolutional coding is r. Therefore, an uncoded bit which is not coded is expressed by (m.sub.0 -m)=(n.sub.0 -n) bits. Among information symbols, a Viterbi algorithm is used for m bits.
A basic rule for a signal space mapping in TCM is that the coded bits are commonly shared, and that in the uncoded bits alone the Euclidean distance du (see FIG. 2C) between different modulation symbols is set to as much as possibly (or is set to a maximum distance). Here, a set of modulation symbols where the coded bits are commonly shared is called a subset.
For example, suppose that a very powerful convolutional code in the course of coding operation is utilized and a coding error rate of the coded bits become "0" in a range beyond a certain C/N (Carrier-to-Noise ratio). Then, the transmission error characteristic is determined only by the Euclidean distance du, so that an optimum signal space mapping can be obtained. Thus, in order to effect such a space mapping, the coded symbols are converted and modulated to a space mapping data Ie/Qe corresponding to respective I/Q axes by a signal space mapping distributor.
FIGS. 2A-2C show construction for a coding of the "Pragmatic Code" and an example of the signal space mapping therefor. Though as the modulation mode there is utilized a Phase Shift Keying (PSK) in a literature by A. J. Viterbi, FIGS. 2A-2C show a case applying to 16-point Quadrature Amplitude Modulation (QAM) (hereinafter referred to as 16 QAM-TCM or simply 16 TCM). In this case, the convolutional coding is performed utilizing the coding rate r=1/2. The coding rate as a whole is 3/4. Thus, 3 bit information can be transmitted as per single modulation symbol. Moreover, the bit number of the uncoded bits is 2 bits, and each subset is comprised of 4 modulation symbols. As for the case applied to 16 QAM, you may refer to G. J. Pottie, D. P. Taylor, "Multilevel Codes Based on Partitioning, Appendix I", IEEE Trans. on Inform. Theory, Vol. 35, No. 1, pp. 96-97, January 1989.
In general, there are 2.sup.n subsets for bit number n of the coded bits, and the number of the modulation symbols constituting each subset is 2 (n.sub.0 -n) against the bit number (n.sub.0 -n) of the uncoded bits, where indicates to a power of 2. Similarly, the modulation symbols which constitute each subset are configured such that the distance between the modulation symbols is maximum. In the case shown in FIG. 2B, the Euclidean distance du equals to 2.times.dc (du=2dc), and an improvement degree of the error rate against the uncoded 16 QAM is approximately 6 dB. Therefore, the coding gain is defined by the improvement degree over the uncoded 8 PSK of 3 bit per symbol, thus being approximately 4 dB.
Next, a decoding technique is described below in the case of 16 TCM with reference to FIG. 3.
FIG. 3 is a block diagram showing construction of a decoder. Referring to FIG. 3, the space mapping data Id/Qd corresponding to the arrangement on the I/Q axes of demodulated received symbols are input, and trellis decoded symbols (x.sub.3, x.sub.2, x.sub.1) are output. As shown in FIGS. 2A-2C, the received symbols are soft-decision decoded in determining the space mapping in each axis, and q=5 for example. On the contrary, q=3 is sufficient in a hard decision of 16QAM. Thus, difference thereof is 2 bits, and the total of 4 bit together with I/Q are soft-decision decoded.
Based on information obtained from the soft decision, four branch metrics to be used for the Viterbi decoding are calculated by a signal space mapping decoding means such as a branch metric unit (referred to as BMU hereinafter). Through the calculation, information bit (x.sub.1) is obtained from a Viterbi decoder. It is to be noted that though the Viterbi decoder usually contains the branch metric unit (BMU), the BMU is depicted as a separate unit from the Viterbi decoder as shown in FIG. 3.
Next, a principle of trellis decoding will be described hereinbelow with reference to FIGS. 4A-4D.
First, the hard decision is performed on each subset and a candidate for decoding symbol, that is, a representative or typical symbol is detected. In other words, since, among trellis coded symbols (y.sub.3 y.sub.2 y.sub.1 y.sub.0), lower two bits can not be determined until Viterbi-decoded, (xxy.sub.1 y.sub.0) is detected in advance as for (y.sub.1 y.sub.0)=(00)-(11).
For example, referring to FIG. 4A, symbol of (1100) becomes the representative symbol for subset symbol which is blank-circled, against the received symbol that is a blackened circle. Similarly, referring to FIGS. 4B-4D, (0101), (1010) and (0011) become the representative symbol, respectively, for each subset. Now, the upper two bits suffice in the detection of the representative symbol, whereas the lower two bits can be determined after the Viterbi decoding process. Thus, the output bit number of the representative symbol will be 2.times.4=8 bits.
The branch metric required for the Viterbi decoding is determined based on the Euclidean distance between each representative symbol and received symbol. Now, branch metrics .lambda..sub.0, .lambda..sub.1, .lambda..sub.2, .lambda..sub.3 corresponding to (y.sub.1 y.sub.0)=(00)-(11) are respectively expressed by Bs bits. For example, Bs may be 4 or 3 (Bs=4 or Bs=3). Utilizing these branch metrics, the error corresponding to possible transmission sequence (path), whose number is Ns, determined by the configuration of the convolutional coding is accumulated and made a path metric. Thereafter, in accordance with the path metric, a path is selected and is stored in a Ms-stage path memory. Among Ns path stored thus, the most probable and likely bit which is stored earliest is output as a Viterbi decoded bit.
As described above, the information bit (x.sub.1) is regenerated while being error-corrected, and after it is convolutional-coded, there is regenerated the coded bit (y.sub.1 y.sub.0). The path memory stages Ms are usually four to six times a constraint length; for example, when the number of states Ns=64, Ms=30 through 40.
The coded bit (y.sub.1 y.sub.0) which is decoded by a circuit shown in FIG. 3, includes error-correcting effect, and by utilizing such effect, uncoded bits (y.sub.3 y.sub.2)=(x.sub.3 x.sub.2) are decoded. Since each detected representative symbol is delayed by as much as the time consumed for being Viterbi-decoded, the symbol is input to a Ms-stage shift register. Thereafter, the bits (y.sub.3 y.sub.2) corresponding to the bits (y.sub.1 y.sub.0) which are thus decoded and regenerated, are selected and the upper two bits of the trellis decoded symbol are determined.
For example, referring to FIGS. 4A-4D, when the outputs of the Ms-stage shift register are (11), (01), (10) and (00), (y.sub.3 y.sub.2)=(x.sub.3 x.sub.2)=(11) if (y.sub.1 y.sub.0)=(00). Therefore, the modulation symbol corresponded in FIG. 4 will be (1100). In other words, even though the modulation symbol turns out to be (1010) by a hard decision of 16 QAM shown in FIG. 4 or FIG. 2, the error is corrected in a manner that In accordance with received sequence about the lower two bits, (1100) is determined correct after all.
Next, drawbacks in the conventional art will be explicitly described hereinbelow. FIG. 5 illustrates a typical uncoded-bit decoding system according to the conventional practice.
In the example shown in FIG. 2B, there are nine ways of possible grouping of representative symbols (J=9). Although it is primarily possible to express by 4 bits (3&lt;log.sub.2 J&lt;4), the output of a representative symbol detecting portion 113 (FIG. 5) is 8 bit and redundant. Particularly, when the representative symbol detecting portion 113 is realized by a ROM (read only memory), a scale of the ROM will be 2.sup.10 .times.8.perspectiveto.8 k bit=16 k transistors; referring to FIG. 5, when T=32 in a T-stage shift register 115 and there are required 22 transistors per single bit, the scale of T-stage shift register will result in 8.times.32.times.22=5632 transistors.
Now, the branch metric is calculated in the course of performing the Viterbi decoding. In the trellis decoding scheme, a square of the Euclidean distance between received symbol and the representative symbol of each subset is used. When this value of the Euclidean distance is directly taken as the branch metric, each branch metric is, for example, expressed by 8 bits. On the other hand, in order to reduce the scale of a branch metric calculating circuit, the bits are often truncated. In other words, when the branch metric unit is constituted by the ROM in the conventional practice, the ROM having 2.sup.10 .times.4.times.4=8192 bits will be necessary if the received symbol which is soft decision made is expressed by 10 bits and the bit truncation is applied to the upper 4 bits. When the ROM having this much scale is built in a trellis decoding LSI (large-scale integration circuit) so as to be a single chip, there is caused inefficiency in its cost performance.